package org.example;

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * 示例 2：
 *
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 *  
 *
 * 提示：
 *
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MergeTwoListsSolution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode resultNode = null;
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode left = l1;
        ListNode right = l2;
        while (left != null || right != null) {
            if (left != null && right != null) {
                if (left.val > right.val) {
                    if (resultNode == null) {
                        resultNode = new ListNode(right.val);
                    } else {
                        setValue(resultNode, right.val);
                    }
                    right = right.next;
                } else {
                    if (resultNode == null) {
                        resultNode = new ListNode(left.val);
                    } else {
                        setValue(resultNode, left.val);
                    }
                    left = left.next;
                }
            } else if (left == null) {
                setValue(resultNode, right.val);
                right = right.next;
            } else {
                setValue(resultNode, left.val);
                left = left.next;
            }
        }
        return resultNode;
    }

    private void setValue(ListNode resultNode, int val) {
        if (resultNode.next == null) {
            resultNode.next = new ListNode(val);
            return;
        }
        setValue(resultNode.next, val);
    }

    /** 测试代码 */
    public static void main(String[] args) {
        ListNode l1 = getListNode(new int[]{1, 2, 4});
        ListNode l2 = getListNode(new int[]{1, 3, 4});
        MergeTwoListsSolution solution = new MergeTwoListsSolution();
        System.out.println(solution.mergeTwoLists(l1, l2));
    }

    private static ListNode getListNode(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        ListNode first = new ListNode(arr[0]);
        for (int i = 1; i < arr.length; i ++) {
            int cur = arr[i];
            ListNode nextNode = new ListNode(cur);
            first.setNext(nextNode);
        }
        return first;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val; this.next = next;
        }
        public void setNext(ListNode nextNode) {
            ListNode cur = this;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = nextNode;
        }
        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}